package 子串.和为k的子数组;

import java.util.HashMap;
import java.util.Map;
/**
 * 题目思路：
 * 前缀和 + HashMap
 * 时间复杂度：O(n)
 * 1，定义前缀和
 * preSum[i] = nums[0] + nums[1] + ... + nums[i]
 * 2，任意一个数组nums[1..r]的和
 * sum(l..r) = preSum[r] - preSum[l-1]
 * 3，我们想要
 * preSum[r] - preSum[l-1] == k
 * preSum[l-1] == preSum[r] - k
 * 一边遍历nums
 * 一边算前缀和preSum
 * 一边用HashMap记录:每个前缀和出现了几次
 * */
/**
 * 思路复用：
 * 和为k的子数组/是否存在/最长长度
 * 且要求子数组是连续的
 * */

class Solution {
    public int subarraySum(int[] nums, int k) {
        // key： 前缀和的值
        // value: 这种前缀和出现的次数
        Map<Integer,Integer> preSumCount = new HashMap<>();
        // 非常重要：前缀和为0出现1次
        // 表示“从开头到当前i，子树组本身就可以等于k”
        preSumCount.put(0,1);
        int preSum = 0;
        int count = 0;
        for(int x : nums){
            preSum += x; // 更新当前的前缀和
            // 我们想找：有多少个之前的前缀和=preSum - k
            int target = preSum - k;
            if(preSumCount.containsKey(target)){
                count += preSumCount.get(target);
            }
            // 把当前的前缀和记录进map
            preSumCount.put(preSum,preSumCount.getOrDefault(preSum,0) + 1);
        }
        return count;
    }
}
